#include <cstddef>
#include <functional>
#include <vector>
using namespace std;
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode *sortList(ListNode *head) {
  vector<ListNode *> v;
  while (head != nullptr) {
    v.push_back(head);
    head = head->next;
  }
  sort(v.begin(), v.end(),
       [](ListNode *a, ListNode *b) { return a->val < b->val; });
  for (int i = 1; i < v.size(); i++) {
    v[i - 1]->next = v[i];
  }
  v[v.size() - 1]->next = nullptr;
  return v[0];
}